package easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 关于递归的练习
 */
public class Recursion {

    public static void main(String[] args) {

//        System.out.println(one(2, 5));

//        System.out.println(two(10, 1));

//        List<Integer> numA = new ArrayList<>();
//        List<Integer> numB = new ArrayList<>();
//        List<Integer> numC = new ArrayList<>();
//        numA.add(4);
//        numA.add(3);
//        numA.add(2);
//        numA.add(1);
//        numA.add(0);
//        System.out.println(numA);
//        hanota(numA, numB, numC);
//        System.out.println(numA);
//        System.out.println(numB);
//        System.out.println(numC);

        TreeNode node1 = new TreeNode(1);

    }

    /**
     * 计算num的exponent的次方
     *
     * @param num
     * @param exponent
     * @return
     */
    public static int one(int num, int exponent) {
        if (exponent == 0) {
            return 1;
        } else {
            return num * one(num, exponent - 1);
        }
    }

    /**
     * 计算等差数列的和
     *
     * @param num
     * @return
     */
    public static int two(int num, int difference) {
        if (num <= 0) {
            return 0;
        } else {
            return num + two(num - difference, difference);
        }
    }

    /**
     * 汉诺塔游戏
     *
     * @param A
     * @param B
     * @param C
     */
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    /**
     * 汉诺塔游戏解决方法
     * 目前我认为，写出递归的步骤为：
     * 1. 归纳方法所需参数
     * 2. 根据分治思想归纳子问题方案
     * 3. 使用递归解决问题
     *
     * @param size
     * @param A
     * @param B
     * @param C
     */
    public static void move(int size, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (size == 1) {
            C.add(A.remove(A.size() - 1));
        } else {
            move(size - 1, A, C, B);
            Integer remove = A.remove(A.size() - 1);
            C.add(remove);
            move(size - 1, B, A, C);
        }
    }

    /**
     * 二叉树结构
     */
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 递归求二叉树所有在[low,high]范围内的节点和
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public int rangeSumBST(TreeNode root, int low, int high) {

//        int sum = 0;
//        if (root.left == null) {
//            return root.val <= low ? root.val : 0;
//        } else if (root.right == null) {
//            return root.val >= high ? root.val : 0;
//        } else {
//            sum += root.val + rangeSumBST(root.left, low, high);
//            return root.val + rangeSumBST(root.right, low, high) + sum;
//        }

        if (root == null) {
            return 0;
        }
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }

    /**
     * 计算树的最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left) + 1;
        int rightDepth = maxDepth(root.right) + 1;
        return leftDepth >= rightDepth ? leftDepth : rightDepth;
    }
}
